/** **********************************************************************************
 * @file    1.C.c
 * @mainpage
 * @date    2013-09-29 23:24
 * @author  Alexey Kulikov <alexeyqu@gmail.com>, group 376, DCAM MIPT
 * @version 1.00
 *
 * Combinatorical weighing
 *
 * @par     The task.
 *          Checks if given mass can be weighed using
 *          linear combination of masses patterned like 4^n, n is non-negative.
 *
 * @note    NB: each mass can be used only once.
 *
 * @warning Mass should be between 0 and 2^31.
**************************************************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

#define DEBUG

#ifdef DEBUG
    #define DBG printf ("# "),
    #define ASSERT(cond)                                                              \
    if (!(cond))                                                                      \
    {                                                                                 \
        printf ("Critical failure in assertion '%s'! \nfile %s, line %d \n"           \
                "Now keep calm and EXTERMINATE! EXTERMINATE! EXTERMINATE!!!\n"        \
                , #cond, __FILE__, __LINE__);                                         \
        abort();                                                                      \
    }
#else
    #define DBG if (0)
    #define ASSERT(cond)
#endif

/** ********************************************************************************
 * Can_Weign - recursively checks if given mass can be weighed
 * (it can be if Mass % 4 == 0, 1, 3)
 *
 * @param   Mass  Mass to check
 *
 * @return  0 - Can
 *          1 - Can not
************************************************************************************/
int Can_Weigh (long long int mass);

int main()
{
    DBG printf ("C language test'07. \n");
    DBG printf ("1.C problem. \n");
    DBG printf ("Check if given mass can be weighed using masses 1, 4, 4^2, ... \n");
    DBG printf ("Enter mass to check: \n-> ");

    long long int mass = 0; //!< Mass to process
    int res_input = 0; //!< Value that controls correct input

    res_input = scanf ("%lld", &mass);
    ASSERT (res_input); ASSERT (mass >= 0); ASSERT (mass <= LONG_MAX);

    DBG printf ("Result: ");

    if (Can_Weigh (mass)) printf ("YES\n");
    else printf ("NO\n");

    return 0;
}

int Can_Weigh (long long int mass)
{
    if (mass == 0) return 1;

    if ((mass % 4) == 2) return 0;

    return Can_Weigh ((mass + 1) / 4);
}
